import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-19
 * Time: 17:40
 */
public class Solution {
    public int count(String str){
        char minChar='z';
        int num=0;
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch<minChar){
                minChar=ch;
                num=1;
            }else if(ch==minChar){
                num+=1;
            }
        }
        return num;
    }

    public int binarySearch(int [] arr,int x){
        int length=arr.length;
        int left=0;
        int right=length-1;
        while(left<=right){
            int mid=(left+right)>>1;
            if(arr[mid]>x){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return length-left;
    }
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int length=words.length;
        int[] result=new int[length];
        for(int i=0;i<length;i++){
            result[i]=count(words[i]);
        }
        Arrays.sort(result);

        int length2=queries.length;
        int[] arr=new int[length2];

        for(int i=0;i<length2;i++){
            int answer=count(queries[i]);
            //二分查找
            int count=binarySearch(result,answer);
            arr[i]=count;
        }
        return arr;
    }
}
